package com.cqs.leetcode.string;


import java.util.*;

/**
 * @author lixiaowen
 * @create 2019-12-15
 */
public class RepeatedDNASequences187 {


    /**
     * hash + 固定窗口
     * @param s
     * @return
     */

    public List<String> findRepeatedDnaSequences(String s) {
        List<String> list = new ArrayList<>();
        if (s == null) return list;
        Map<String,Integer> freq = new HashMap<>(s.length());
        int size  = 10;
        for (int i = 0; i <= s.length() - size ; i++) {
            String str = s.substring(i, i + size);
            Integer cnt = freq.getOrDefault(str,0);
            if (cnt == 1){
                //遍历一次 且避免重复添加
                list.add(str);
            }
            freq.put(str, cnt + 1);
        }
        return list;
    }


    public List<String> findRepeatedDnaSequencesBit(String s) {
        List<String> list = new ArrayList<>();
        if (s == null || s.length() < 10) return list;
        int mask = (1 << 18) - 1;
        char[] chars = s.toCharArray();
        int val = 0;//字符串转化为十进制
        for (int i = 0; i < 9; i++) {
            val <<= 2;
            val += transfer(chars[i]);
        }
        byte[] fre = new byte[1 << 20];
        for (int i = 9; i < chars.length; i++) {
            //低18位（后18各字符）
            val &= mask;
            val = (val << 2) + transfer(chars[i]);
            int cnt = fre[val];
            if (cnt == 1) {
                list.add(s.substring(i - 9, i + 1));
            }
            fre[val] = (byte) Math.min(cnt + 1, 2);
        }
        return list;
    }

    private int transfer(char c) {
        switch (c) {
            case 'A':
                return 0;
            case 'C':
                return 1;
            case 'G':
                return 2;
            case 'T':
                return 3;
            default:
                throw new IllegalArgumentException();
        }
    }

    public static void main(String[] args) {
        String str = "AAAAAAAAAA";
        RepeatedDNASequences187 repeat = new RepeatedDNASequences187();
        List<String> list = repeat.findRepeatedDnaSequences(str);
        list = repeat.findRepeatedDnaSequencesBit(str);
        System.out.println(list);
    }
}
